import java.util.Arrays;

/**
 * Created by xiebang
 * Description
 * User:小谢
 * Date:2021-10-12
 * Time:17:53
 */
public class TestHeap {
    public  int[] elem;
    public int usedSize;

    public TestHeap() {
        this.elem = new int[10];
    }

    public  void crateBigHeap(int[] array){
        //把需要的数据放到elem里，
        for (int i= 0; i < array.length;i++){
            this.elem[i] = array[i];
            this.usedSize++;
        }
        for (int parent = (this.usedSize - 1 - 1)/2;parent >= 0;parent--){
                shiftDowm(parent);
        }
    }
    public void createBigHeap1(int[] array){
        int parent = (array.length - 1 - 1) / 2;
        for (int i = parent; i >= 0 ; i--) {
            shiftDown2(i);
        }
    }
    public void shiftDown2(int parent){
        int child = 2 * parent + 1;
        //当孩子节点的下标超过堆的长度调整结束
        while (child < this.usedSize){
            //得到孩子节点中的最大值
            if (child + 1 < this.usedSize && this.elem[child] < this.elem[child + 1]){
                child++;
            }
            //与父亲节点进行比较，若大于就进行交换
            if (this.elem[child] > this.elem[parent]){
                int tmp = this.elem[child];
                this.elem[child] = this.elem[parent];
                this.elem[parent] = tmp;
                parent = child;
                child = 2 * parent + 1;
            }else {
                break;
            }
        }
    }
    public void shiftDowm(int parent){
        int child = 2*parent + 1;
        //进入循环说明你有左孩子
        while ((child < this.usedSize)){
            if (child+1 <this.usedSize && this.elem[child] < this.elem[child+1]){
                child++;
            }
            //child为孩子的最大值
            if (this.elem[child] > this.elem[parent]){
                int tmp = this.elem[parent];
                this.elem[parent] = this.elem[child];
                this.elem[child] = tmp;
                parent = child;
                child = 2*parent +1;
            }else {
                break;//如果孩子节点比父亲节点小就直接跳出
            }
        }


    }
    public void myShiftDowm(int parent){
        int child = 2*parent + 1;
        while (child < this.usedSize-1) {
            if (child + 1 < this.usedSize - 1 && this.elem[child] < this.elem[child + 1]) {
                child++;
            }

            if (this.elem[parent] < this.elem[child]){
                int tmp = this.elem[parent];
                this.elem[parent] = this.elem[child];
                this.elem[child] = tmp;
                parent = child;
                child = parent * 2 + 1;
            }else {
                break;
            }
        }

    }
    public boolean isFull(){
        return this.usedSize == this.elem.length;
    }

    public void push(int val){
        if (isFull()){
            this.elem = Arrays.copyOf(this.elem,2*this.usedSize);
        }
        this.elem[this.usedSize] = val;
        this.usedSize++;
        shitfUp(this.usedSize-1);
    }
    public void push1(int val){
        if (isFull()){
            this.elem = Arrays.copyOf(this.elem,2*this.usedSize);
        }
        this.elem[this.usedSize] = val;
        this.usedSize++;
        shitfUp1(this.usedSize-1);
    }
    public void shitfUp1(int child){
        int parent = (child - 1) / 2;
        while (parent >= 0){
            if (this.elem[parent] < this.elem[child]){
                int tmp = this.elem[parent];
                this.elem[parent] = this.elem[child];
                this.elem[child] = tmp;
                child = parent;
                parent = (child - 1) / 2;
            }else {
                break;
            }
        }
    }
    public void shitfUp(int child){
        int parent = (child-1)/2;
        while (parent >= 0){
            if (this.elem[child] >this.elem[parent]){
                int tmp = this.elem[child];
                this.elem[child] = this.elem[parent];
                this.elem[parent] = tmp;
                child = parent;
                parent  = (child-1)/2;
            }else {
                break;
            }
        }
    }
    public  boolean isEmpty(){
        return this.usedSize == 0;
    }
    public void poll(){
        if (isEmpty()){
            throw  new RuntimeException("队列为空");
        }
        int tmp = this.elem[usedSize-1];
        this.elem[usedSize-1] = this.elem[0];
        this.elem[0] = tmp;
        this.usedSize--;

        shiftDowm(0);
    }
    public void poll1(){
        if (isEmpty()){
            throw  new RuntimeException("队列为空");
        }
        int tmp = this.elem[this.usedSize - 1];
        this.elem[this.usedSize - 1] = this.elem[0];
        this.elem[0] = tmp;

        this.usedSize--;
        shiftDown2(0);
    }

    public int peek(){
        if (isEmpty()){
            throw  new RuntimeException("队列为空");
        }
        return this.elem[0];
    }
    public void heapSort(){
        int end = this.usedSize - 1;
        while (end>0){
            int top = this.elem[0];
            this.elem[0] = this.elem[end];
            this.elem[end] = top;
            this.usedSize--;
            shiftDowm(0);
            end--;
    }

}
    public void show(){
        for (int i = 0; i < this.elem.length; i++) {
            System.out.println(this.elem[i] + " ");
        }
    }
}




















